package com.wz.leetcode.linkedlist;

import java.util.PriorityQueue;

public class MergeKSortedLists {

    PriorityQueue<Node> minHeap = new PriorityQueue<>();

    public ListNode mergeKLists(ListNode[] lists) {
        for (ListNode n : lists) {
            if (n != null) {
                minHeap.offer(new Node(n.val, n));
            }
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (!minHeap.isEmpty()) {
            Node n = minHeap.poll();
            tail.next = n.p;
            tail = tail.next;
            if (n.p.next != null) {
                minHeap.offer(new Node(n.p.next.val, n.p.next));
            }
        }
        return head.next;
    }

    class Node implements Comparable<Node> {
        int val;
        ListNode p;

        Node(int val, ListNode p) {
            this.val = val;
            this.p = p;
        }

        // 最小堆
        public int compareTo(Node other) {
            return this.val - other.val;
        }
    }
}
